`:top
Die Klasse `*Pr`* der `!μ-rekursiven Funktionen`! oder `!partiell-rekursiven Funktionen`! spielt in der `F33f`_`[Rekursionstheorie`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Rekursionstheorie]`_`f, einem Teilgebiet der `F33f`_`[theoretischen Informatik`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Theoretische_Informatik]`_`f, eine wichtige Rolle (`!µ`! für `F33f`_`[griechisch`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Neugriechische_Sprache]`_`f μικρότατος ‚das kleinste‘). Nach der `F33f`_`[Church-Turing-These`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Church-Turing-These]`_`f beschreibt sie die Menge aller Funktionen, die im intuitiven Sinn `F33f`_`[berechenbar`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Berechenbarkeit]`_`f sind. Eine wichtige echte `F33f`_`[Teilmenge`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Teilmenge]`_`f der μ-rekursiven Funktionen sind die `F33f`_`[primitiv-rekursiven Funktionen`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Primitiv-rekursive_Funktion]`_`f.
Die Klasse der μ-rekursiven Funktionen stimmt überein mit der Klasse der `F33f`_`[Turing-berechenbaren`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Turing-Berechenbarkeit]`_`f Funktionen sowie weiteren gleich mächtigen Berechenbarkeitsmodellen, wie dem `F33f`_`[Lambda-Kalkül`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Lambda-Kalkül]`_`f, `F33f`_`[Registermaschinen`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Registermaschine]`_`f und `F33f`_`[WHILE-Programmen`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=WHILE-Programm]`_`f.
Die primitiv-rekursiven Funktionen sind aus einfachen Grundfunktionen (konstante 0-Funktion, Projektionen auf ein Argument und Nachfolgerfunktion) durch Komposition und primitive Rekursion aufgebaut. Dadurch erhält man immer totale Funktionen, also Funktionen im eigentlichen Sinn. Die μ-rekursiven Funktionen sind demgegenüber `F33f`_`[partielle Funktionen`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Partielle_Funktion]`_`f, die aus denselben Konstrukten und zusätzlich durch die Anwendung des μ-Operators gebildet werden können. Durch die Anwendung des μ-Operators wird Partialität eingeführt. Jedoch ist nicht jede μ-rekursive Funktion nicht-total. Beispielsweise sind alle primitiv-rekursiven Funktionen auch μ-rekursiv. Ein Beispiel für eine nicht primitiv-rekursive, totale, μ-rekursive Funktion ist die `F33f`_`[Ackermannfunktion`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Ackermannfunktion]`_`f.
>>Contents
• `F0af`_`[Definition des μ-Operators`#definition-des-operators]`_`f
• `F0af`_`[Definition der μ-rekursiven Funktionen`#definition-der-rekursiven-funktionen]`_`f
• `F0af`_`[Äquivalenz der μ-rekursiven Funktionen mit der Turingmaschine`#quivalenz-der-rekursiven-funktionen-mit-der-turingmaschine]`_`f
• `F0af`_`[Bemerkung`#bemerkung]`_`f
• `F0af`_`[Beispiele`#beispiele]`_`f
• `F0af`_`[Literatur`#literatur]`_`f
-─
>>Definition des μ-Operators
Für eine partielle Funktion f : : N k + 1 → → N {\\displaystyle f\\colon \\mathbb {N} ^{k+1}\\to \\mathbb {N} } und natürliche Zahlen x 1 ; … … ; x k ∈ ∈ N {\\displaystyle x_{1};\\dots ;x_{k}\\in \\mathbb {N} } sei die Menge
M ( f , x 1 , … … , x k ) = { n ∈ ∈ N ∣ ∣ f ( x 1 , … … , x k , n ) = 0 ∧ ∧ ∀ ∀ 0 ≤ ≤ m ≤ ≤ n : : f ( x 1 , … … , x k , m ) ↓ ↓ } {\\displaystyle M(f,x_{1},\\dots ,x_{k})=\\{n\\in \\mathbb {N} \\mid f(x_{1},\\dots ,x_{k},n)=0\\ \\land \\ \\forall 0\\leq m\\leq n\\colon f(x_{1},\\dots ,x_{k},m)\\downarrow \\}}
festgehalten, also die Gesamtheit aller n {\\displaystyle n} derart, dass f {\\displaystyle f} an der Stelle ( x 1 , … … , x k , n ) {\\displaystyle (x_{1},\\dots ,x_{k},n)} identisch 0 verschwindet und zusätzlich für alle Punkte ( x 1 , … … , x k , m ) {\\displaystyle (x_{1},\\dots ,x_{k},m)} mit m ≤ ≤ n {\\displaystyle m\\leq n} definiert ist.
Zu beachten ist dabei, dass M ( f , x 1 , … … , x k ) {\\displaystyle M(f,x_{1},\\dots ,x_{k})} als Menge `F33f`_`[natürlicher Zahlen`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Natürliche_Zahl]`_`f genau dann ein `F33f`_`[Minimum`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Größtes_und_kleinstes_Element]`_`f besitzt, wenn sie nicht leer ist (vgl. `F33f`_`[Wohlordnung`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Wohlordnung]`_`f).
Durch Anwendung des μ μ {\\displaystyle \\mu } -Operators auf f {\\displaystyle f} entstehe nun die partielle Funktion μ μ f : : N k → → N {\\displaystyle \\mu f\\colon \\mathbb {N} ^{k}\\to \\mathbb {N} } , definiert durch:
μ μ f ( x 1 , … … , x k ) = { min M ( f , x 1 , … … , x k ) , falls M ( f , x 1 , … … , x k ) ≠ ≠ ∅ ∅ undefiniert sonst {\\displaystyle \\mu f(x_{1},\\dots ,x_{k})={\\begin{cases}\\min M(f,x_{1},\\dots ,x_{k}),&{\\text{falls }}M(f,x_{1},\\dots ,x_{k})\\neq \\emptyset \\\\{\\text{undefiniert}}&{\\text{sonst}}\\end{cases}}}
Insbesondere bildet der Operator μ μ {\\displaystyle \\mu } also eine ( k + 1 ) {\\displaystyle (k+1)} -stellige partielle Funktion auf eine k {\\displaystyle k} -stellige partielle Funktion ab.
Für berechenbares f {\\displaystyle f} kann das Programm zur Berechnung von μ μ f {\\displaystyle \\mu f} verstanden werden als eine `F33f`_`[While-Schleife`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=While-Schleife]`_`f, die nach oben zählt und die deswegen nicht `F33f`_`[terminieren`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Terminiertheit]`_`f muss:
Parameter: x 1 , … … , x k {\\displaystyle x_{1},\\ldots ,x_{k}} .
Setze n {\\displaystyle n} auf 0 {\\displaystyle 0} ;
Solange f ( x 1 , … … , x k , n ) ≠ ≠ 0 {\\displaystyle f(x_{1},\\dots ,x_{k},n)\\neq 0} , erhöhe n {\\displaystyle n} um 1 {\\displaystyle 1} ;
Ergebnis: n {\\displaystyle n} .
>>Definition der μ-rekursiven Funktionen
Die Klasse P r {\\displaystyle Pr} der μ-rekursiven Funktionen ( N k → → N {\\displaystyle \\mathbb {N} ^{k}\\to \\mathbb {N} } ) umfasst die folgenden Grundfunktionen:
1. konstante 0-Funktion: f k ( n 1 , … … , n k ) := 0 {\\displaystyle f^{k}\\left(n_{1},\\dots ,n_{k}\\right):=0}
2. Projektion auf ein Argument: π π i k ( n 1 , … … , n k ) := n i {\\displaystyle \\pi _{i}^{k}\\left(n_{1},\\dots ,n_{k}\\right):=n_{i}} , 1 ≤ ≤ i ≤ ≤ k {\\displaystyle 1\\leq i\\leq k}
3. Nachfolgefunktion: ν ν ( n ) := n + 1 {\\displaystyle \\nu \\left(n\\right):=n+1}
Die μ-rekursiven Funktionen erhält man als Abschluss der Grundfunktionen bezüglich der drei folgenden Operationen:
1. der Komposition: f ( n 1 , … … , n k ) := g ( h 1 ( n 1 , … … , n k ) , … … , h m ( n 1 , … … , n k ) ) {\\displaystyle f\\left(n_{1},\\dots ,n_{k}\\right):=g\\left(h_{1}\\left(n_{1},\\dots ,n_{k}\\right),\\dots ,h_{m}\\left(n_{1},\\dots ,n_{k}\\right)\\right)} , falls g , h 1 , … … , h m ∈ ∈ P r {\\displaystyle g,h_{1},\\dots ,h_{m}\\in Pr}
2. der primitiven Rekursion: f ( 0 , n 2 , … … , n k ) := g ( n 2 , … … , n k ) {\\displaystyle f\\left(0,n_{2},\\dots ,n_{k}\\right):=g\\left(n_{2},\\dots ,n_{k}\\right)} und f ( n 1 + 1 , n 2 , … … , n k ) := h ( f ( n 1 , … … , n k ) , n 1 , … … , n k ) {\\displaystyle f\\left(n_{1}+1,n_{2},\\dots ,n_{k}\\right):=h\\left(f\\left(n_{1},\\dots ,n_{k}\\right),n_{1},\\dots ,n_{k}\\right)} , falls h , g ∈ ∈ P r {\\displaystyle h,g\\in Pr}
3. des μ-Operators.
>>Äquivalenz der μ-rekursiven Funktionen mit der Turingmaschine
Es lässt sich beweisen, dass eine `F33f`_`[Turingmaschine`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Turingmaschine]`_`f (TM) durch μ-rekursive Funktionen simuliert werden kann. Es lässt sich auch beweisen, dass die Menge der μ-rekursiven Funktionen genau der Menge der Turing-berechenbaren Funktionen entspricht.
`!Beweis-Skizze für die Simulation der TM mit μ-rekursiven Funktionen`!
Man kann zeigen, dass sich die Konfiguration einer TM durch drei Zahlen a {\\displaystyle a} , b {\\displaystyle b} , c {\\displaystyle c} darstellen lässt.
Genau so kann eine Funktion h ( a , b , c ) = y {\\displaystyle h(a,b,c)=y} (eine bijektive Abbildung N 3 → → N {\\displaystyle \\mathbb {N} ^{3}\\to \\mathbb {N} } ) definiert werden,
die eine geeignete Kodierung der TM ist.
Nehmen wir also eine primitiv-rekursive Funktion
f ( n , x ) = y {\\displaystyle f(n,x)=y} ,
die eine geeignete Kodierung der TM liefert für die Eingabe x {\\displaystyle x} nach n {\\displaystyle n} Berechnungsschritten,
und eine zweite primitiv-rekursive Funktion
g ( y ) = 0 ∨ ∨ g ( y ) = 1 {\\displaystyle g(y)=0\\lor g(y)=1} ,
die für eine Kodierung y {\\displaystyle y} als Ergebnis 0 liefert, falls y {\\displaystyle y} einen Endzustand der TM repräsentiert, und ansonsten 1.
Dann ergibt
A n z a h l ( x ) = μ μ ( g ( f ( n , x ) ) ) {\\displaystyle \\mathrm {Anzahl} (x)=\\mu (g(f(n,x)))}
die Anzahl der Schritte, die eine TM zur Berechnung bis zum Ende benötigt. Also bekommen wir mit
B e r e c h n u n g ( x ) = f ( A n z a h l ( x ) , x ) {\\displaystyle \\mathrm {Berechnung} (x)=f(\\mathrm {Anzahl} (x),x)}
die Berechnung der TM in einem Endzustand bei der Eingabe x {\\displaystyle x} .
>>Bemerkung
• Die Berechenbarkeit einer μ-rekursiven Funktion bezieht sich auf Werte aus ihrem Definitionsbereich. Es existiert kein allgemeines Verfahren, das alle Werte liefert, die nicht zum Definitionsbereich einer μ-rekursiven Funktion gehören.
• Der μ-Operator realisiert einen `*Suchprozess`*, der genau dann abbricht, wenn der gesuchte Wert existiert.
>>Beispiele
• Alle primitiv-rekursiven Funktionen sind μ-rekursiv.
• Die `F33f`_`[Ackermannfunktion`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Ackermannfunktion]`_`f und die `F33f`_`[Sudanfunktion`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Sudanfunktion]`_`f sind totale μ-rekursive Funktionen, die nicht primitiv-rekursiv sind.
• Die Funktion `F33f`_`[Fleißiger Biber`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Fleißiger_Biber]`_`f (busy beaver) ist nicht μ-rekursiv.
• Die Folge der Ziffern der Halte-Wahrscheinlichkeit (`F33f`_`[Chaitinsche Konstante`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Chaitinsche_Konstante]`_`f Ω Ω {\\displaystyle \\Omega } ) ist nicht μ-rekursiv. Die Halte-Wahrscheinlichkeit ist definiert durch
Ω Ω := ∑ ∑ p 2 − − | p | {\\displaystyle \\Omega :=\\sum _{p}2^{-\\left|p\\right|}} ,
wobei p {\\displaystyle p} ein haltendes Programm ist und | p | {\\displaystyle \\left|p\\right|} die Länge des Programms in `F33f`_`[Bit`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Bit]`_`f bezeichnet.
>>Literatur
• `F33f`_`[Heinz-Dieter Ebbinghaus`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Heinz-Dieter_Ebbinghaus]`_`f, Jörg Flum, Wolfgang Thomas: `*Einführung in die mathematische Logik`* (= `*Spektrum-Hochschultaschenbuch.`*). 4. Auflage. Spektrum – Akademischer Verlag, Heidelberg u. a. 1996, ISBN 3-8274-0130-5.
• `F33f`_`[Hans Hermes`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Hans_Hermes]`_`f: `*Aufzählbarkeit, Entscheidbarkeit, Berechenbarkeit. Einführung in die Theorie der rekursiven Funktionen`* (= `*Heidelberger Taschenbücher.`* 87). 2. Auflage. Springer, Berlin u. a. 1971, ISBN 3-540-05334-4.
• `F33f`_`[Arnold Oberschelp`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Arnold_Oberschelp]`_`f: `*Rekursionstheorie.`* BI-Wissenschaftlicher-Verlag, Mannheim u. a. 1993, ISBN 3-411-16171-X.
• `F33f`_`[Wolfgang Rautenberg`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Wolfgang_Rautenberg]`_`f: Einführung in die Mathematische Logik. Ein Lehrbuch. 3., überarbeitete Auflage. Vieweg + Teubner, Wiesbaden 2008, ISBN 978-3-8348-0578-2.
`c`F0af`_`[↑ Back to top`#top]`_`f`a